package leetcode.year2021.month10;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

//  114. 二叉树展开为链表

// 方法1 ： 前序遍历该二叉树，将所有节点存储在List中，然后再取出遍历
public class _26_01Flatten114 {

  public void flatten(TreeNode root) {
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root);
    TreeNode prev = null;

    while (!stack.isEmpty()){
      TreeNode curr = stack.pop();
      if (prev != null){
        prev.right = curr;
        prev.left = null;
      }

      TreeNode left = curr.left;
      TreeNode right = curr.right;

      if (right != null){
        stack.push(right);
      }
      if (left != null){
        stack.push(left);
      }

      prev = curr;
    }
  }

//  public void flatten(TreeNode root) {
//    TreeNode curr = root;
//    while (curr != null) {
//      if (curr.left != null) {
//        TreeNode next = curr.left;
//        TreeNode predecessor = next;
//        while (predecessor.right != null) {
//          predecessor = predecessor.right;
//        }
//        predecessor.right = curr.right;
//        curr.left = null;
//        curr.right = next;
//      }
//      curr = curr.right;
//    }
//  }

//  public void flatten(TreeNode root) {
//    if (root == null){
//      return;
//    }
//    // 方法2 ： 前序遍历，在遍历的同时，展开，还是使用栈(模拟递归)，先进后出
//    Deque<TreeNode> treeNodes = new LinkedList<>();
//    treeNodes.add(root);
//    TreeNode prev = null;
//
//    while (treeNodes.size() > 0){
//      TreeNode curr = treeNodes.pop();
//      if (prev != null){
//        prev.left = null;
//        prev.right = curr;
//      }
//      TreeNode right = curr.right;
//      TreeNode left = curr.left;
//      if (right != null){
//        treeNodes.push(right);
//      }
//      if (left != null){
//        treeNodes.push(left);
//      }
//      prev = curr;
//    }
//  }


//  public void flatten(TreeNode root) {
//    // 方法1 ： 前序遍历该二叉树，将所有节点存储在List中，然后再取出遍历
//    ArrayList<TreeNode> treeNodes = new ArrayList<>();
//    flattenDfs(root,treeNodes);
//    for (int i = 0; i < treeNodes.size()-1; i++) {
//      TreeNode curr = treeNodes.get(i);
//      curr.left = null;
//      curr.right = treeNodes.get(i+1);
//    }
//  }
//
//  private void flattenDfs(TreeNode root, ArrayList<TreeNode> treeNodes) {
//    if (root == null){
//      return;
//    }
//    treeNodes.add(root);
//    flattenDfs(root.left,treeNodes);
//    flattenDfs(root.right,treeNodes);
//  }

  /**
   * 给你二叉树的根结点 root ，请你将它展开为一个单链表：
   *
   * 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
   * 展开后的单链表应该与二叉树 先序遍历 顺序相同。
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   *
   * 输入：root = [1,2,5,3,4,null,6]
   * 输出：[1,null,2,null,3,null,4,null,5,null,6]
   * 示例 2：
   *
   * 输入：root = []
   * 输出：[]
   * 示例 3：
   *
   * 输入：root = [0]
   * 输出：[0]
   *
   * 来源：力扣（LeetCode）
   * 链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
   * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
   */

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
